package com.java.comprehensive.arithmetic.leecode.easy;

import com.google.gson.Gson;
import util.ListNode;

/**
 * @program: comprehensive-service
 * @description: 合并两个有序链表
 * @author: 窦绍飞
 * @create: 2021-11-03 17:47
 **/
public class LeetCode_21 {
	public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		} else if (list2 != null) {
			return list1;
		} else if (list1.val < list2.val) {
			list1.next = mergeTwoLists(list1.next, list2);
			return list1;
		} else {
			list2.next = mergeTwoLists(list1, list2.next);
			return list2;
		}
	}

	public static ListNode mergeTwoLists_2(ListNode list1, ListNode list2) {
		//创建哑结点
		ListNode dummy = new ListNode(-1);
		ListNode prev = dummy;
		while (list1 != null && list2 != null) {
			if (list1.val <= list2.val) {
				prev.next = list1;
				list1 = list1.next;
			} else {
				prev.next = list2;
				list2 = list2.next;
			}
			prev = prev.next;
		}
		prev.next = list1 == null ? list2 : list1;
		return dummy.next;
	}

	public static void main(String[] args) {
		ListNode listNode1 = new ListNode(1);
		ListNode listNode2 = new ListNode(2);
		ListNode listNode3 = new ListNode(4);
		ListNode listNode4 = new ListNode(1);
		ListNode listNode5 = new ListNode(3);
		ListNode listNode6 = new ListNode(4);
		listNode2.next = listNode3;
		listNode1.next = listNode2;
		ListNode l1 = listNode1;
		listNode5.next = listNode6;
		listNode4.next = listNode5;
		ListNode l2 = listNode4;
		ListNode listNode = mergeTwoLists_2(l1, l2);
		Gson gson = new Gson();
		System.out.println(gson.toJson(listNode));
	}
}
